It has long been recognized that the speed of a computer memory system can be increased through the use of a relatively high speed, low capacity buffer store. That is, if a high speed buffer is implemented properly in a computer system, main memory speed will appear to approach that of the buffer. For example, in a case where the cycle time of the buffer is one-tenth of that of the main memory, the effective access time may be eight to nine times less than that of the main memory. The underlying reason for this speed-up of operation is that experience has shown that data currently being processed have a high probability of being used again in the near future and that related data is commonly stored in contiguous address locations in the main memory.
The manner in which so-called "cache" buffers have been implemented in various IBM computer systems has been described in a number of published technical articles. For example, reference is made to the article by J. S. Liptay entitled, "Structural Aspects of the System/360 Model 85, II the Cache", IBM Systems Journal, Vol. 7, No. 1, pp 15-21; that by D. H. Gibson entitled "Considerations in Block-Oriented Systems Design", Spring Joint Computer Conference 1967; and that by C. J. Conti et al entitled "Structural Aspects of the System/360 Model 85, I General Organization", IBM Systems Journal, Vol. 7, No. 1, 1968. In the IBM System 360-Model 85, store operations always cause the main memory to be directly updated. If the main storage sector being changed has a sector in the buffer assigned to it, the buffer is also updated; otherwise, no activity related to the buffer takes place. Therefore, store operations cannot cause a buffer sector to be reassigned, a block to be loaded, or the activity list controlling the replacement algorithm to be revised.
The present invention is considered to be a significant improvement over the memory hierarchy employed in the IBM system. In accordance with the teachings of the present invention, one or more processor units and/or Input-Output devices are adapted to receive instructions and operands (hereinafter collectively referred to as "data") from a main memory only by way of a high speed buffer memory. Also, data from the processors and/or I/O units to be stored in the main memory must pass through the high speed buffer memory. Thus, the buffer of the present invention will hereinafter be termed a "Storage Interface Unit" or "SIU".
The SIU of the present invention is a high-speed (low cycle time) storage buffer designed to reduce the overall storage delay time of a computing system by automatically allowing the great majority of storage references to take place in the SIU proper, rather than in the lower speed (higher cycle time) main memory or backing store. In the preferred embodiment of the present invention, this is accomplished by providing circuitry (hardware) to transfer an 8-word block of data into the SIU whenever any word from that block is required by a processor or input/output unit. This block becomes one of several blocks remaining resident in the SIU until it is displaced by a new current block as determined by a suitable replacement algorithm.
The SIU of the present invention employs a so-called set-associative storage buffer. In an exemplary arrangement, the buffer may comprise 4,096 words of storage which may be divided into 128 sets, each set consisting of four 8-word blocks of data. The main memory employed in the system is then also divided into 128 sets, each set containing 1/128 of the words in the total main memory address range. Alternatively, the buffer may be expanded to contain additional words of storage divided into a larger number of sets with each set consisting of four 8-word blocks of data. In this alternative arrangement, the main memory would also be divided into an identical number of sets but each set would include a lesser number of 8-word blocks. Any one of the 8-word blocks in a given main memory set may be placed in any one of the four 8-word blocks in the corresponding SIU set. When a transfer (either a read or a write) is made between the SIU and main storage, an 8-word block from contiguous addresses is transferred during a single main memory cycle.
When a request for a word from storage is made by a processor or an input/output unit, this request is seen only by the SIU. Conventional direct address selection is used to address the one of 128 sets in which the required word is located. This selection causes the SIU to simultaneously read the address of each of the four blocks currently resident in the set and to compare each with the requested address. If one of the four block addresses matches the requested address, the appropriate word is read from that block and sent to the requesting unit. If none of the four block addresses matches, an immediate request is made by the SIU to the main memory for the entire block which contains the desired word. While waiting for this new block of data, the SIU determines which of the four current blocks is the least recently used and marks it for replacement. Next, the SIU checks the block to be replaced to determine whether any word in that block has been modified while resident in the SIU. If a modification had occurred, the entire block plus its address is read into a temporary holding register in the SIU so that it can be restored to the main memory as soon as the current main memory cycle is finished. When the data arrives from the main memory, it is stored into the now-vacated block and the appropriate word is ultimately sent by the SIU to the original requestor to complete the cycle.
In prior art computing systems wherein high speed buffers are employed to increase the throughput of the system, store operations always cause the main memory to be updated. If the main memory set being changed has a corresponding set in the buffer assigned to it, the buffer is also updated. That is, each time a processor or I/O unit effects a write operation, the main memory must be updated immediately. Since the main memory operates at a relatively long cycle time, frequent references to main memory slow down the overall processing speed of the system.
The system of the present invention utilizes what is termed a "post-store" method to obviate this problem. Rather than making a write reference to the main memory each time a write is effected in the SIU buffer memory, in the system of the present invention the main memory is only updated when the address to be modified is not resident in the buffer and a block containing altered data, i.e., data different from what is in its corresponding block in main memory is selected for replacement. Upon detecting that a desired address is not resident in the SIU buffer, the SIU immediately sends a "read" request to the main memory to obtain the entire block in which the desired address is located. Simultaneously the SIU, through a replacement algorithm, determines which of the blocks currently in the buffer memory is to be replaced. A check is made to determine if this selected block had its contents modified while resident in the buffer and if so, the entire block plus its address is gated into a temporary holding register. While the new block is being brought into the buffer from the main memory and stored in the now-vacated block location, the displaced block contained in the holding register is written back into the main memory, thereby updating the main memory.
The economy in time occasioned by this "post-store" method is readily apparent. Rather than requiring a relatively slow main memory cycle each time a change is made in a block stored in the buffer to update the main memory as in prior art systems, in the system of this invention only one main memory cycle is used to update main memory and this only occurs when a block is selected for replacement which had its contents modified while it was resident in the buffer. However, while resident in the buffer, this block may have undergone many, many modifications before being selected for replacement.